∂18-DEC-74  0133		network site SRI
 Date: 18 DEC 1974 0127-PST
 From: GARVEY at SRI-AI
 Subject: CHAPTER 1
 To:   TOB at SU-AI
 cc:   TENENBAUM
 
 TOM, HERE IS THE CURRENT VERSION OF CHAPTER 1. THERE ARE STILL A FEW 
 POINTS TO BE ADDED, BUT THEY WILL PROBABLY WAIT UNTIL MORE OF THE REST
 IS DONE. I'LL APPRECIATE YOUR FEEDBACK.
 
 
 
 
 
 
 I.	INTRODUCTION
 
 
 This  thesis reports recent experimental results with a
 computer based system that can be rapidly programmed to
 find specified objects in relatively complex real-world
 environments.   Objects are designated to the system by
 circling  examples  with a cursor in a displayed image.
 The object is then characterized by histograms of local
 surface  attributes  such as hue and orientation and by
 spatial    relationships    among     the     surfaces.
 The  system  then formulates a strategy for finding the
 object  based  on  knowledge   of   available   picture
 processing  techniques  and  about  the  makeup  of the
 current pictorial domain.   The  resulting  program  is
 then   run   on   representative  scenes  and  debugged
 interactively as errors materialize.
 
 	Our system is based on the premise that in real scenes there
 exist easy ways of "seeing" things.  The many contextual relations among
 real-world objects, together with multisensory
 (i.e., range and color) data, suggest that a combination of perceptual
 cues can be found that would enable the system to easily locate and
 identify a given object.  For example, to locate a tabletop, it is usually
 sufficient to find a horizontal surface 2-1/2 feet above the floor since
 these features distinguish tables from other objects.  And to find a
 telephone, it is usually easier to first find the table, and then to
 find the telephone as a small compact mass of black points on the table,
 instead of attempting the much harder task of finding a telephone solely on
 the basis of its shape (the principal basis in past scene-analysis
 systems) using no contextual aids.  However, even when such complicated
 features as shape are required, if the context is suitably limited, a
 simple distinguishing measure related to that feature may suffice to
 resolve remaining recognition ambiguities.  Thus, the ratio of maximum
 height to base surface area is sufficient to distinguish the
 shape of a telephone from that of other black objects normally found on
 a desk top (e.g., loose-leaf binders). We call this approach to
 perception, "vision by distinguishing features".
 
 These  example  strategies  are  admittedly  ad hoc and
 highly context dependent.    We strongly  believe  that
 the  effective use of such domain specific knowledge is
 essential for machine perception.  Of course, the  most
 successful  existing  scene analysis programs also rely
 heavily on ad hoc heuristics. The  distinction  between
 these  programs  and  the  approach we advocate lies in
 generality. Programs based on a large amount of ad  hoc
 knowledge  were  thought  to  be  "cheats"  because the
 knowledge  was  inflexibly   embedded.    Thus,   minor
 modifications   of  the  object  or  environment  often
 necessitated major programming.
 
 A system must instead be supplied with the higher level
 knowledge  and  problem-solving  capabilities needed to
 choose for itself the most effective way of finding any
 object   in   any   context,  utilizing  all  currently
 available knowledge about the world. Specifically,  the
 computer  must  use its knowledge to select features of
 the desired object that  are  both  distinguishing  and
 easy    to    see.            The   utility   of   such
 "distinguishing features" is  critically  dependent  on
 what  is  known  at  the  current  stage  of  analysis.
 Hence,  it  is   unreasonable   to   preprogram   these
 recognition strategies, except in the simplest and most
 static environments.
 
 
 II.	BACKGROUND
 
 	Until recently, research on machine perception has concentrated
 on the exhaustive description of simple geometric environments appearing
 in a black-and-white television image.  **REF**  The "blocks" world
 was originally chosen to simplify the problems of feature extraction
 and thus to accelerate the development of high-level perception programs.
 Unfortunately, it may also have impeded progress by diverting investigators
 to difficult but less important problems attributable to its very sterility.
 First, the lack of variety and of meaningful contextual constraints in
 this artificial world limited the extent to which perceptual strategies
 could capitalize on task goals and expectations; exhaustive descriptions
 were invariably sought.  Moreover, the unavailability of attributes like
 color and texture led to preoccupation with articulated boundary descriptions
 (i.e., shape) as the principal basis for recognition.  This preoccupation,
 in turn, diverted a disproportionate amount of effort to
 the problem of extracting perfect line drawings of homogeneous
 objects viewed under homogeneous, shadowless illumination.
 
 -----------------------------------------------------------------------
 * References are listed at the end of the thesis.
 -----------------------------------------------------------------------
 
 	The ad hoc, primarily bottom-up, techniques developed under
 these constraints were unsatisfying because they would be overwhelmed
 by the irrelevant detail found in virtually any other type of scene.
 Highly tuned edge followers, for example, suffocate in a world with
 texture.  Moreover, the elaborate topological descriptions that conveniently
 characterized simple polyhedra are inappropriate for many real-world
 objects (e.g., trees, lakes) even if they could be obtained with reasonable
 effort.
 
 	The thesis confronts several important perceptual issues, 
 such as information overload and generality of strategies, that
 arise in real world scenes.  Instead of simplifying the environment,
 our system copes with the complexity of real-world scenes by capitalizing
 upon their natural redundancy of descriptive features and contextual
 constraints.
 
 		We have chosen SRI office scenes as a research domain,
 because they are naturally complex, semantically rich, and experimentally
 convenient.  Many of the lessons initially learned in this office should
 prove applicable generally to complex scenes with adequate semantic
 richness; for example, the analysis of outdoor scenes and earth resource
 satellite imagery.
 
 		Our objective is to find designated objects in uncluttered
 office environments like that shown in Figure --- using brightness,
 color, and range as sensory inputs.  The system will show its comprehension
 by outlining the indicated object in a displayed image of the scene.
 
 		Our system is roughly partitioned into a low-level
 section consisting of a set of primitive perceptual operators (collectively
 known as ISIS) and a high-level perceptual executive.  The executive
 knows about many kinds of things:  about perceptual properties of objects, 
 about their contextual relations, about the operating characteristics
 of the available primitive operators, and about partial results generated
 by an ongoing analysis.  The task of the executive is to combine these
 various kinds of information in order to define the next step of analysis;
 that is, to define which operator should be next applied to which portion
 of the scene.
 
 
 III.	DESIGN CONSIDERATIONS
 
 	The above point of view suggested the following design 
 considerations and implementations for our perceptual system.
 
 	A.	Perception as Problem Solving
 
 		Perception should be construed as a problem-solving
 process; the system must utilize its knowledge of the current
 real-world environment and of its own perceptual capabilities to plan
 where and how to look for a specified object.  Specifically, the computer
 must use its knowledge to select features of the desired object that
 are both distinguishing and easy to see.  The utility of such "distinguishing
 features" is critically dependent on what is known att the current stage
 of analysis.  Hence, it is unreasonable to preprogram these recognition
 strategies, except in the simplest and most static environments.  Moreover,
 a system that can plan its own strategy has inherent generality; it should
 be able to function in any environment for which its knowledge base and
 perceptual primitives are adequate.
 
 	Our system contains a strategy generating program which plans
 to a sufficient level of detail to begin execution. Fine details are
 planned when required by the execution of a coarse planning step.
 
 	B.	Sequential Decision Paradigm
 
 		It is usually unnecessary to examine all features of an
 object to arrive at a confident recognition hypothesis.  Perception
 should proceed like the game of 20 questions.  Simple descriptive
 attributes (e.g., color, size) rapidly limit consideration to a small
 subset of the objects possible in a given environmental context. 
 Remaining ambiguities can then be resolved using distinguishing components
 of more complex attributes (e.g., shape).
 
 	The system generates predicates which check sufficient local
 features to either identify the surface in question, or to reduce the
 set of possible ambiguous objects to the point that a small number of
 global distinguishing tests can disambiguate.
 
 	C.	Multiple Sensors
 
 		The likelihood of finding suitable surface attributes
 for distinguishing a given object increases with the number of independent
 sensory modalities.  Furthermore, simple discrimination in each of several
 sensory modalities should be a cheaper, more reliable alternative to
 using more detailed descriptions is a single modality.  It is substantially
 easier to interpret a set of brightness observed through several filters
 as a color, or a set of range values as a surface orientation, than
 to interpret a set of grey-scale intensities as a shape or texture.
 
 	Our programs make use of color information (represented
 as hue and saturation components), range information (from which
 is extracted height and local surface orientation), and intensity
 data (grey-level data taken though a neutral density filter).
 
 	D.	Goal Directed Feature Extraction
 
 		A key problem is doing perception by distinguishing
 features is to extract the features reliably.  One lesson that has been
 learned in a decade of vision research is that feature extraction
 cannot be adequately performed bottom-up as a preliminary to a
 knowledge-based interpretative process *ref* (WINSTON).  Rather, the 
 system must be
 integrated so that recognition strategies are based on knowledge of
 which features are easy to extract in a given environmental context.
 The low-level routines should then concentrate on extracting those specific
 features.
 
 		Global surface features like shape are the hardest
 to extract because the surface must first be segmented from the rest of
 the scene.  Fortunately, with multisensory data, we can rely heavily
 on local surface attributes known to be both homogeneous over the goal
 object and distinguished from those of other nearby surfaces previously
 found or anticipated in the environment.
 
 	The planner uses its knowledge of the costs of the various
 available perceptual procedures to organize its search to examine 
 cheap attributes first, later resorting to more complex and 
 expensive tests.
 
 	E.	Incremental Acquisition of Knowledge
 
 		The substantial amount of ad hoc world knowledge required
 to plan perceptual strategies is most reasonably acquired in an
 incremental fashion. Insufficient information is usually indicated
 by a strategy failure. In this case, it is usually easy to determine
 the problem and add enough new facts to allow the system to replan
 a correct distinguishing strategy.
 
 	The perceptual system is embedded in ISIS (Appendix ---),
 which gives the user full interactive capabilities for examining the
 attributes of a point or a region and to add or modify information in 
 appropriate data structures.
 
 IV.	PERCEPTUAL STRATEGY
 
 	The writing of a perceptual system to locate objects in scenes
 required the implementation of certain high-level capabilities.
 First, the system required the ability to locate single, isolated
 sufaces of objects. Then, from known surfaces and known relationships
 among object parts, the system needed to be able to locate other parts.
 Finally, we required the ability to use information about one object
 to find other objects.
 
 	The search for an object proceeds in three phases:
 acquisition, validation, and outlining.  During acquisition, the multisensory
 image is sampled for characteristic surface attributes of the desired
 object.  If a sample satisfying all criteria is found, a sequence of
 top-down validation tests determines whether the acquired sample does,
 in fact, belong to the desired object or to another object with similar
 surface characteristics.
 
 	A.	Acquisition
 
 	The objective in acquisition is to rapidly
 disqualify obviously irrelevant areas of the scene so that subsequent
 processing can concentrate on the most promising locations for the goal
 object.  This objective is realized by sampling the scene at a 
 density determined by the goal object's size, maximum range, and
 least favorable viewing orientation.  Attributes of the goal object are
 tested at each sample in an order likely to cause the earliest
 disqualification of irrelevant points.  The selection of attributes suitable
 for acquisition is based on such considerations as:
 
 		(1) 	Criteriality--the attribute should invariably
 			be associated with the object (e.g., the floor
 			is always horizontal).
 
 		(2)	Distinguishability--the attributes should not
 			also be characteristic of other objects expected
 			in that context.
 
 		(3)	Measurability--the attribute should be reliably
 			obtained from simple, localized processing of
 			sensory data.
 
 		Acquisition can also be done indirectly, as in the example
 of locating the telephone by first locating the table.  That is, clues
 for locating the target object, or for narrowing the search space,
 can be provided by some other previously located object with a known
 relationship to the target.
 
 	B.	Validation
 
 	The second phase of the strategy scheme,
 validation, provides increased confidence that the acquired samples belong
 to the target.  This happens in two ways.  First, the target object may
 be ambiguous with respect to other known objects.  In this case, the
 system attempts to distinguish the target from other members of this set.
 Second, the system then tries to raise its confidence that the acquired
 points belong to the correct object by making other tests.  This phase
 of validation is necessary for two reasons:  First, acquisition attempts
 to distinguish samples of the target from samples of other known objects,
 and therefore, some attempt must be made to guard against unknown objects.
 Second, since objects are characterized rather coarsely, there may
 be points on the object which are not reflected in the model.  Unexpected
 spurious points of this type are filtered out by this second validation 
 stage.
 
 		Validation tests can also include more global features
 too costly to test at each sample:  e.g., global attributes (such as
 size and shape) of the surface surrounding the acquisition sample.  We
 rely on the consensus of several crude, individually tolerant tests
 related to the surface attributes, rather than actually extracting a
 detailed description of any particular one.  For example, the ratio of
 perimeter squared to area, or of length to width, might suffice as 
 representations of shape.  Many global attributes of a surface can be
 grossly tested even without finding a detailed boundary.  For instance,
 a surface can be disqualified as too small merely by failing to find a
 sufficient number of appropriate samples within a gross window centered
 on the acquisition sample.
 
 	C.	Outlining
 
 	To complete its objective, the system must
 finally display an outline of the object it has found.  The system can
 use several techniques to determine the outline of the object from
 previously validated kernal points.  The simplest is a region growth
 process which applies a predicate to neighboring points, keeping
 those that pass and recursively applying the predicate to their neighbors.
 
 		The system can also utilize high-level knowledge about
 a scene to rapidly obtain approximate boundaries of located objects without
 exhaustive low-level operations (such as edge following or region growing
 followed by line fitting).  An entity in the scene is completely mapped
 onto a rigid object model by supplying the model's identity and a sufficient
 set of correspondences between model points and image points to constrain
 position and orientation.  Detailed boundaries are then obtained by
 projecting the model onto the scene using computer graphics techniques.  
 
 *****************************************************************
 Indirect find -- to be added
 *****************************************************************
 
 
 V.	EXAMPLE (to be rewritten)
 
 	We will use the example of finding the chair in the image of
 Figure --- to illustrate the process outlined above.
 
 	The system knows that the two main parts of the chair are the
 seat and the back.  It decides on the basis of both ease of execution
 and its estimate of how finding one part will aid in finding the other,
 to first try to locate the chair seat.  From its models, it determines
 that a good distinguishing feature of the seat is its local surface
 orientation (horizontal), and its height above the floor (18").  As
 shown in Figure ---, the image is then randomly sampled at a density
 consistent with the generated predicate, the chair seat's surface description,
 and its expected size.  The predicate is applied to each sample, and those
 for which pass the predicate is true are collected together (as
 shown in Figure---) to form the set of acquired points for the
 chair seat.  These points are validated and then used as starting
 points for a region grower which completes the seat outline shown in
 Figure ---.
 
 	The system uses the seat to constrain its search for the back
 of the chair.  In this example, it windows the image.  That is, it
 selects a subimage around the seat region it just located.  This
 window is then randomly sampled (as shown in Figure ---), and filtered
 by the predicate for chair back.  For acquiring the chair back, the
 system creates a predicate which checks hue, orientation, and height.
 The resulting acquired samples are shown in Figure ---.  After validation,
 the remaining samples are used to grow the region shown in Figure ---.
 The resulting outline of the seat and back are shown in Figure ---.
 
 VI.	OVERVIEW OF THE THESIS
 
 	To be added at end of writing (when overview is known).
 
 
 
 
 SEE YOU FRIDAY MORNING.
 TOM
 -------